

class bronKerboschCliqueFinder(object):
    ''' Bron-Kerbosch classic algorithm that finds all the maximal cliques in a graph (i.e. cliques that cannot be expanded) '''
    def find(self,a_graph):
        self.cliques = []
        self.graph = a_graph
        potential_clique = []
        candidates = list(a_graph.nodes())
        already_found = []
        self._find_cliques(potential_clique,candidates,already_found)
        
    def _find_cliques(self,potential_clique, candidates, already_found):
        candidate_list = list(candidates)
        if self.halt_search(candidates, already_found)==False:
            for candidate in candidate_list:
                potential_clique.append(candidate)
                candidates.remove(candidate)
                new_candidates = []
                for new_candidate in candidates:
                    if self.graph.has_edge(candidate, new_candidate):
                        new_candidates.append(new_candidate)
                new_already_found = []
                for already_found_node in already_found:
                    if self.graph.has_edge(candidate, already_found_node):
                        new_already_found.append(already_found_node)
                
                if len(new_already_found)==0 and len(new_candidates)==0:
                     # Clique found
                     self.cliques.append(list(potential_clique))               
                else:
                    self._find_cliques(potential_clique, new_candidates,new_already_found)
                
                # After checking all the cliques with candidate, can move it to already found
                already_found.append(candidate)
                potential_clique.remove(candidate)

    def halt_search(self,candidates, already_found):
        for already_found_node in already_found:
            edge_counter = 0
            for candidate in candidates:
                if self.graph.has_edge(already_found_node,candidate):
                    edge_counter = edge_counter +1
            if edge_counter==len(candidates):
                return True
        return False
#    
#    
#    def find_k_cliques(self,a_graph,k):
#        ''' Find all the cliques of size k (maximal and not maximal) '''
#        self.cliques = []
#        self.graph = a_graph
#        potential_clique = []
#        candidates = list(a_graph.nodes())
#        already_found = []
#        self._find_cliques(potential_clique,candidates,already_found)        
